二元堆積樹（Heap）的筆記

學習影片

https://www.youtube.com/watch?v=klbGg8dmYTM

基本定義

• Heap（堆積） 是一種完全二元樹（Complete Binary Tree），表示為二元樹，但在樹中的節點安排上有特別的優先級順序。
• 堆積分為 最大堆（Max-Heap） 和 最小堆（Min-Heap）：
  • 最大堆：每個節點的值都大於或等於其子節點的值，即根節點是整棵樹中的最大值。
  • 最小堆：每個節點的值都小於或等於其子節點的值，即根節點是整棵樹中的最小值。

特點

• 完全二元樹：堆積是一種完全二元樹，這意味著它所有的層次都是完全填滿的，除了最後一層，節點是從左至右依序填入。
• 節點索引特性（陣列表示）：
  • 堆積樹通常使用陣列來表示，其中節點的索引可以用數學公式推算：
    • 節點 i 的 左子節點：2 * i + 1
    • 節點 i 的 右子節點：2 * i + 2
    • 節點 i 的 父節點：(i - 1) // 2
  • 這種表示方式讓插入與刪除操作更方便，並能節省儲存結構。

操作時間複雜度

• 插入 和 刪除最大值或最小值：O(log n)
  • 插入時，透過「向上堆積調整（heapify-up）」來保持堆積特性。
  • 刪除時，透過「向下堆積調整（heapify-down）」來保持堆積特性。
• 搜尋：O(n)
  • 由於堆積不保證順序性，搜尋可能需要遍歷所有節點，時間複雜度為 O(n)。

堆積的應用

優先順序佇列（Priority Queue）：
* 優先順序佇列是一種特殊的佇列，每次取出優先順序最高的元素。
* 使用最大堆或最小堆可以實現優先順序佇列，最大堆取出最大值，最小堆取出最小值。

• Heap Sort 排序演算法：
  • 使用堆積進行排序的一種演算法，透過反覆將最大或最小值取出來構建有序數列。
  • Heap Sort 的時間複雜度為 O(n log n)，是穩定排序演算法之一。
• 圖演算法中的應用：
  • 在 Dijkstra 最短路徑演算法 和 Prim 最小生成樹演算法 中，Heap 常被用來快速找到最小權重的邊或節點。

常用操作

1. 插入操作（Insertion）：
   • 將新元素加入堆積的最後一個位置，然後執行向上堆積調整（heapify-up），直到滿足堆積特性。
   • 步驟：
     1. 將新元素放在樹的最後（即陣列的最後）。
     2. 比較新元素與其父節點，如果不符合堆積特性（父節點比子節點小於或大於），則交換位置。
     3. 重複這個過程，直到元素放在正確的位置。
2. 刪除操作（Deletion）：
   • 刪除最大堆的最大值（根節點）或最小堆的最小值（根節點），然後將堆積的最後一個元素移到根節點，執行向下堆積調整（heapify-down）。
   • 步驟：
     1. 取出堆積的根節點（最大或最小值）。
     2. 將堆積的最後一個節點移動到根節點位置。
     3. 比較根節點與其子節點，交換不符合堆積特性的節點。
     4. 重複這個過程，直到樹恢復堆積特性。
3. 建立堆積（Build Heap）：
   • 將一組無序的數列轉換為堆積，透過「自底向上」的方法進行調整。
   • 步驟：
     1. 找到所有非葉節點，從最右邊的非葉節點開始向下調整。
     2. 執行向下堆積調整（heapify-down），直到整棵樹成為最大堆或最小堆。

最大堆與最小堆操作範例

假設我們有一個陣列 [4, 10, 3, 5, 1]，我們希望把它轉換成最大堆：
步驟 1：建構最大堆
* 將 [4, 10, 3, 5, 1] 插入到堆積樹中：
* 根節點：10
* 左子節點：5
* 右子節點：3
* 左子節點的左子節點：4
* 左子節點的右子節點：1
* 經過調整，形成的最大堆為：

     10
    /  \
   5    3
  / \
 4   1

步驟 2：插入一個新節點（例如：7）

• 新節點 7 插入到最左邊的空位置，即 4 的左邊：

     10
    /  \
   5    3
  / \
 7   1

• 進行向上堆積調整（heapify-up），與其父節點 5 交換：

     10
    /  \
   7    3
  / \
 5   1

注意事項

• 完全二元樹結構：要維持堆積的完全二元樹結構，即所有節點要依序填滿，不能出現某一層有空位而下一層有節點的情況。
• 平衡性與效率：Heap 不必像 AVL 樹或紅黑樹那樣維持嚴格的平衡性，因此插入與刪除操作在一般情況下的效率較高，但搜尋時間較長。